package Test07;

import java.util.ArrayList;

class ElemType<T extends Comparable<T>> {
    T key; // 关键字域
    // 其它域

    public ElemType() {
        key = null;
    }

    public ElemType(T data) {
        key = data;
    }
}

public class SeqTable<T extends Comparable<T>> {
    protected final int MAXSIZE = 100;
    protected ArrayList<ElemType<T>> elem; // 数据元素存储空间基址
    protected int length; // 表长度

    public SeqTable(T[] data, int n) {
        elem = new ArrayList<ElemType<T>>(MAXSIZE);
        ElemType<T> e;
        for(int i = 0; i < n; i++) {
            e = new ElemType<T>(data[i]);
            elem.add(i, e);
        }
        length = n;
    }

    public int Search_Seq(T key) {
        int i;
        ElemType<T> e = new ElemType<T>(key);
        elem.add(length, e); // "哨兵"
        for (i = 0; elem.get(i).key.compareTo(key) != 0; ++i); // 从前往后找
        if(i < length) return i;
        else return -1;
    }

    public int Search_Bin(T key) {
        int low, high, mid;
        low = 0; high = length - 1; // 置区间初值
        while (low <= high) {
            mid = (low + high) / 2;
            if (key.compareTo(elem.get(mid).key) == 0)
                return mid; // 找到待查元素
            else if (key.compareTo(elem.get(mid).key) < 0)
                high = mid - 1; // 继续在前半区间进行查找
            else
                low = mid + 1; // 继续在后半区间进行查找
        }
        return -1; // 顺序表中不存在待查元素
    }
    

    public void Insert(T key) {
        int i;
        for(i = elem.size() - 1; i >= 0; i--)
            if((elem.get(i).key.compareTo(key)) < 0)
                break;
        ElemType<T> e = new ElemType<T>(key);
        elem.add(i + 1, e);
    }
}